package toOffer;

import java.util.Arrays;

/**
 * <h3>toOffer</h3>
 *
 * @author YuanAo
 * @date 2024/5/14 17:26
 * @description <p></p>
 */

/**
 * 题目：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 *
 * 请必须使用时间复杂度为 O(log n) 的算法。
 */
public class No35 {
    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 7};
        int target = 0;
        int result = searchInsert(nums, target);
        System.out.println(result);
    }

    public static int searchInsert(int[] nums, int target) {
        if (target < nums[0]) return 0;
        if (target > nums[nums.length - 1]) return nums.length;

        // 能到这里的target的值肯定比nums[0]大、比最大的num[]要小
        int search = Arrays.binarySearch(nums, target);
        // search值小于0说明没有在nums里找到对应的数
        if (search < 0){
            // 搜索值不是数组元素，且在数组范围内，从1开始计数，得“ - 插入点索引值”；
            return -search - 1;
        }

        return search;
    }

    /**
     * 二分查找
     * 前提条件：数组有序
     *
     * 四种情况：
     * （1）target大小在nums数组大小的范围内、且能找到相同的数，返回索引
     * （2）target大小在nums数组大小的范围内，不能找到相同的数，返回 能插入位置的相反数，即 -插入位置 （能插入位置指：把这个数插入进原数组不破坏数组排序）
     * （3）target小于数组最小值，返回
     * @param nums
     * @param target
     * @return
     */
    public static int binarySearch(int[] nums, int target){


        return 0;
    }
}
